package com.ming.learn.from.carl.linkedlist;

/*
第707题：设计链表
 */
public class Of20201221LeetCode707 {
    /*
    在链表类中实现这些功能：
        get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
        addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
        addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
        addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
        deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
     */
    public static void main(String[] args) {
        MyListNode myListNode = new MyListNode();
        myListNode.addAtHead(1);
        myListNode.printLinkedList();// 1
        myListNode.addAtTail(3);
        myListNode.printLinkedList();// 1 3
        myListNode.addAtIndex(1,2);
        myListNode.printLinkedList();// 1 2 3
        System.out.println(myListNode.get(1));// 2
        myListNode.deleteAtIndex(1);
        myListNode.printLinkedList();// 1 3
        System.out.println(myListNode.get(1));// 3
    }
}

class MyListNode{

    private Node dummyHead;
    private int length;

    public MyListNode() {
        length=0;
        dummyHead=new Node(0);
    }
    int get(int index){
        Node cur=dummyHead.next;
        if (index>(length-1)||index<0){
            return -1;
        }
        for (int i = 0; i < index; i++) {
            cur=cur.next;
        }
        return cur.val;
    }
    void addAtHead(int val){
        Node newHead = new Node(val);
        newHead.next= dummyHead.next;
        dummyHead.next=newHead;
        length++;
    }
    void addAtTail(int val){
        Node node = new Node(val);
        Node cur = dummyHead.next;
        while (cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
        length++;
    }

    void deleteAtIndex(int index){
        if (index<0||index>=length){
            return;
        }
        Node cur = dummyHead;
        while ((index--)>0){
            cur=cur.next;
        }
        cur.next=cur.next.next;
        length--;
    }

    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果index大于链表的长度，则返回空
    void addAtIndex(int index,int val){
        if (index>length){
            return;
        }
        Node node = new Node(val);
        Node cur=dummyHead;
        while ((index--)>0){
            cur=cur.next;
        }
        node.next=cur.next;
        cur.next=node;
        length++;
    }


    // 打印链表
    void printLinkedList() {
        Node cur= dummyHead;
        while (cur.next!=null){
            cur=cur.next;
            System.out.print(cur.val+"\t");
        }
        System.out.println();
    }

    class Node{
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }

        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
    }
}
